class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < n - 2;) {
            //初步判断
            if (nums[i] > 0) {
                return ret;
            }
            int l = i + 1;
            int r = n - 1;
            while (l < r) {
                if (nums[l] + nums[r] < -nums[i]) {
                    l++;
                } else if (nums[l] + nums[r] > -nums[i]) {
                    r--;
                } else {
                    ret.add(new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[r])));
                    //满足还需要找
                    l++;
                    r--;
                    //去重
                    while (l < r && nums[l] == nums[l - 1])
                        l++;
                    while (r > l && nums[r] == nums[r + 1])
                        r--;
                }
            }
            //i也需要去重
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
}